// Copyright 2013 The go-algs Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package bit contains some bit twiddling methods from various resources.
package bit

// CountBits counts the number of set bits (1) in an array of bytes.
// See the bc subroutine for Brian Kernighan's method.
func CountBits(d []byte) int64 {
	c := make([]int64, 256)
	for i := range d {
		c[int(d[i])] += 1
	}
	t := int64(0)
	for i := range c {
		if c[i] > 0 {
			t += c[i] * bc(byte(i))
		}
	}
	return t
}

// bc is Brian Kernighan's method for counting the number of set bits.
// Source: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
func bc(b byte) int64 {
	c := int64(0)
	for {
		if b == 0 {
			return c
		}
		b &= b - 1
		c++
	}
	panic("unreachable")
}
